import os
import sys
from time import clock

class sortNode:
    def __init__(self):
        self.value = 0.0
        self.index = 0

def cmp(x, y):
    if x.value > y.value:
        return 1
    if x.value == y.value:
        return 0
    else:
        return -1

class Node:
    def __init__(self, id):
        self.id = id
        self.sparent = None
        #self.dict = {}
        self.merge = 0.0
        self.ratio = 0.0
        self.list = []
        self.focus = False
    def parent(self):
        if self.sparent != None:
            #print self.dict['parent'].id
            #print self.list
            return self.sparent
    def append(self, child):
        child.sparent = self

class Tree:
    def __init__(self):
        self.currentlevel = 0
        self.merged = False
        self.leaves = []
        self.nodemap = []
        self.main_cluster = 99999
        self.new_comer = {}
        self.cluster_occupy = {}
    def load(self, n):
        i = 0
        self.currentlevel = n - 1
        #print 'currentlevel', self.currentlevel
        self.merged = False
        self.leaves = []
        for i in range(n):
            #print 'i ' + str(i)
            self.nodemap.append(i)
        #self.nodemap[n - 1] = self.leaves
        i = 0
        while i < n:
            node = Node(int(i))
            node.list.append(i)
            self.leaves.append(node)
            #print node.list
            i = i + 1
        self.nodemap[n - 1] = self.leaves
        #print n, self.nodemap[n - 1]
    def getCluster(self, vm, level):
        if level < 0 or level > len(self.nodemap):
            return None
        tp = self.leaves[vm]
        i = len(self.nodemap)
        while i > level:
            tp = tp.parent()
            i = i - 1
        return tp
    def getClusterCenter(self, vm, level):
        if level < 0 or level > len(self.nodemap):
            return None
        tp = self.leaves[vm]
        i = len(self.nodemap)
        while i > level:
            tp = tp.parent()
            i = i - 1
        while i >= 0:
            if i >= len(self.cluster_occupy):
                i = i - 1
                continue
            if self.cluster_occupy[i] in tp.list:
                return self.cluster_occupy[i]
            tp = tp.parent()
            i = i - 1
        return -1
    def inSameCluster(self, i, j, level):
        if j == -1: return False
        if level < 0 or level > len(self.nodemap):
            return False
        #print i, j
        #print self.leaves
        tpi = self.leaves[i]
        tpj = self.leaves[j]
        i = len(self.nodemap) - 1
        while i >= level:
            if tpi.id == tpj.id:
                return True
            tpi = tpi.parent()
            tpj = tpj.parent()
            #print tpi.id,
            #print tpj.id
            i = i - 1
        return False
    def labelCluster(self, si):
        i = len(self.nodemap) - 2
        while i >= 0:
            #self.cluster_occupy[i] = si
            if si in self.new_comer[i] and not self.new_comer.has_key(i):
                self.cluster_occupy[i] = si
            i = i - 1
    def merge(self, i, j, value):
        if self.merged:
            #print 'No need to merge...' 
            return
        #print 'Begin to merge...'
        layer = []
        iterator = 0
        skip = -1
        #print 'MERGING LEVEL ' + str(self.currentlevel)
        while iterator <= self.currentlevel:
            if skip == iterator:
                iterator = iterator + 1
                continue
            node = Node(len(layer))
            if iterator == i or iterator == j:
                nodei = self.nodemap[self.currentlevel][i]
                nodej = self.nodemap[self.currentlevel][j]
                node.merge = value
                node.append(nodei)
                node.append(nodej)
                for element in nodei.list:
                    node.list.append(element)
                for element in nodej.list:
                    node.list.append(element)
                node.list.sort()
                self.new_comer[self.currentlevel - 1] = node.list
                skip = i + j - iterator
                self.new_comer[self.currentlevel - 1] = node.list
                layer.append(node)
            else:
                nodei = self.nodemap[self.currentlevel][iterator]
                node.list = nodei.list
                node.append(nodei)
                layer.append(node)
            iterator = iterator + 1
        self.currentlevel = self.currentlevel - 1
        #print 'currentlevel', self.currentlevel
        self.nodemap[self.currentlevel] = layer
        if self.currentlevel == 0:
            self.merged = True
    def output(self):
        #print self.nodemap
        print '----------Partition Tree----------'
        #print self.nodemap
        k = 0
        for nodelist in self.nodemap:
            print '\nlevel ' + str(k) #level
            for node in nodelist:
                print '[', #cluster
                for single_node in node.list:
                    print single_node, #node
                print '] ',
            k = k + 1
        print

class vm:
    def __init__(self):
        self.quantity = 0
        self.vms = []
        self.matrix = []
        self.ptree = Tree()
        self.focus = []
        self.grouplevel = 0
        self.values = {}
    def load(self, file):
        loader = open(file, 'r')
        lines = loader.readlines()
        for line in lines:
            tricell = line.split()
            #print tricell
            if len(tricell) == 2:
                self.quantity = int(tricell[0])
                #print self.quantity
                for vmi in range(self.quantity):
                    #print vmi, 'added'
                    self.vms.append(vmi)
                    self.matrix.append([])
                    for vmj in range(self.quantity):
                        self.matrix[vmi].append(0)
                continue
            if len(tricell) == 3:
                #if int(tricell[0]) == 0 or int(tricell[1]) == 0:
                #    continue
                tri1 = int(tricell[0])
                tri2 = int(tricell[1])
#                if not (tri1) in self.vms:
#                    self.vms.append(tri1)
#                if not (tri2) in self.vms:
#                    self.vms.append(tri2)
                #if self.matrix.has_key(tri1):
                self.matrix[tri1][tri2] = float(tricell[2])
                #else:
                #    self.matrix[tri1] = {}
                #    self.matrix[tri1][tri2] = float(tricell[2])
            else:
                continue
        #print 'VMs loaded...\n'
        self.vms.sort()
        print self.vms
        self.ptree.load(len(self.vms))
        loader.close()
    def cal(self, clusteri, clusterj):
        aver = 0.0
        for vmi in clusteri.list:
            #fstkey = self.vms[vmi]
            for vmj in clusterj.list:
                #seckey = self.vms[vmj]
                #if self.matrix.has_key(fstkey):
                #    if self.matrix[fstkey].has_key(seckey):
                aver = aver + self.matrix[vmi][vmj]
                #if self.matrix.has_key(seckey):
                #    if self.matrix[seckey].has_key(fstkey):
                aver = aver + self.matrix[vmj][vmi]
        #print aver
        aver = aver / (len(clusteri.list) * len(clusterj.list))
        return aver
    def pick_nearest(self, vmlist):
        #print 'pick from '
        #for item in vmlist:
        #    print item.list
        i = 0
        j = 0
        resi = 0
        resj = 1
        maximum = 0.0
        #print len(vmlist)
        for clusteri in vmlist:
            j = 0
            for clusterj in vmlist:
                if i == j:
                    j = j + 1
                    continue
                value = 0.0
                value = self.cal(clusteri, clusterj)
                #print value
                #print 'cal: ' + str(i) + ' ' + str(j) + '(' + str(value) + ')'
                if value > maximum:
                    resi = i
                    resj = j
                    maximum = value
                j = j + 1
            i = i + 1
        #print 'caled'
        #print 'picked nearest pair: ' + str(resi) + ' ' + str(resj) + ' ' + str(maximum)
        return [resi, resj, maximum]
    def partition(self, lvl_finite=1):
        #print self.quantity
        #self.ptree.load(len())
        sortlit = []
        while not self.ptree.merged:
            #print 'pick'
            res = self.pick_nearest(self.ptree.nodemap[self.ptree.currentlevel])
            #print 'picked'
            sele = sortNode()
            sele.index = self.ptree.currentlevel - 1
            sele.value = res[2]
            sortlit.append(sele)
            #print 'merge'
            self.ptree.merge(res[0], res[1], res[2])
            #print 'merged'
        #print
        previous = -1.0
        for sn in sortlit:
            if previous == -1.0:
                previous = sn.value
                sn.value = 999999.0
            else:
                temp = sn.value
                if previous == 0.0:
                    sn.value = 999999.0
                else:
                    sn.value = sn.value / previous
                previous = temp
            #print 'level ' + str(sn.index) + ' ' + str(sn.value)
        sortlit.sort(cmp)
        i = 0
        self.sortlist = sortlit
    def changeFocus(self, sfocus):
        i = 0
        self.focus = []
        self.ptree.main_cluster = 99999
        for element in self.sortlist:
            #self.focus.append(element.index)
            #print 'level ' + str(element.index) + ' ' + str(element.value)
            i = i + 1
            if i <= sfocus:
                self.focus.append(element.index + 1)
                if element.index + 1 < self.ptree.main_cluster:
                    self.ptree.main_cluster = element.index + 1
        self.grouplevel = self.ptree.main_cluster
    def output(self):
        print self.vms
        self.ptree.output()

#c1 = clock()
#entity = vm()
#entity.load('../vm.in')
#entity.partition()
##entity.output()
#print 'getCluster: '
#gt = entity.ptree.getCluster(0, 5)
#print gt.id
#print gt.list
#print entity.ptree.inSameCluster(4, 11, 4)
#print clock() - c1